#include <algorithm>
using namespace std;
class Solution {
    vector<vector<int> > ans;
    vector<int> cur;
    void run(int n, vector<int> &S) {
        if (n==S.size()) {
            ans.push_back(cur);
            return;
        }
        int m=n;
        while (m+1<S.size() && S[m+1]==S[n]) ++m;
        run(m+1, S);
        for (int i=n;i<=m;i++) {
            cur.push_back(S[i]);
            run(m+1, S);
        }
        for (int i=n;i<=m;i++) cur.pop_back();
    }
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        ans.clear();
        cur.clear();
        run(0, S);
        return ans;
    }
};
